package src.数据结构.链表.单向链表;

import src.数据结构.链表.Node;

public class LinkList<T> {
    protected Node head; // 头节点
    protected int N; // 链表长度

    public LinkList() {
        // 初始化链表
        this.head = new Node<>(null, null);
        this.N = 0;
    }


    // 判断表是否为空
    public boolean isEmpty() {
        return this.N == 0;
    }

    // 获取表大小
    public void size() {
        System.out.println("元素个数：" + this.N);
    }

    // 返回指定索引的值
    public T get(int index) {
        // 循环查询
        Node<T> n = head.next;
        if (index > 0 && index < this.N) {
            for (int i = 0; i < index; i++) {
                n = n.next;
            }
        }
        return n.item;
    }

    // 插入数据
    public void add(T t) {
        // 找到当前最后一个节点
        Node<T> n = head;
        while (n.next != null) {
            n = n.next;
        }
        // 创建临时节点，保存元素T
        Node<T> tNode = new Node<>(t, null);
        // 当前最后一个节点指向新节点
        n.next = tNode;
        this.N++;
    }

    public void insert(int i, T t) {
        /* 找到i位置前一个节点 */
        Node<T> pre = head;
        for (int j = 0; j < i; j++) {
            pre = pre.next;
        }
        /* 找到i位置的一个节点 */
        Node<T> curr = pre.next;
        /* 创建新节点并指向i位置节点 */
        Node<T> tNode = new Node<>(t, curr);
        // old1 -> p -> old2
        /* i位置前一个节点指向新节点 */
        pre.next = tNode;
        this.N += 1;
    }

    // 删除数据
    public T pop(int index) {
        // 找到index前一个节点
        Node<T> pre = head;
        for (int j = 0; j < index; j++) {
            pre = pre.next;
        }
        // 找到index节点
        Node<T> curr = pre.next;
        // 找到index位置下一个节点
        Node nextNode = curr.next;
        // 前一个节点指向下一个节点
        pre.next = nextNode;

        this.N--;
        return curr.item;
    }

    public T pop() {
        /* 尾删 */
        // 特殊情况处理，如果链表为空，返回 null
        if (head == null) {
            return null;
        }

        // 找到尾节点的前一个节点
        Node<T> pre = head;
        for (int j = 0; j < this.N - 1; j++) {
            pre = pre.next;
        }

        // 找到尾节点
        Node<T> curr = pre.next;

        // 如果只有一个节点，将头节点置为 null
        if (N == 1) {
            head = null;
        } else {
            // 前一个节点的 next 指针置为 null
            pre.next = null;
        }

        this.N--;
        return curr.item;
    }

    // 清空数据
    public void clear() {
        this.head = null;
        this.N = 0;
    }

    // 查询元素的索引
    public int indexOf(T t) {
        // 从头节点开始比较
        Node<T> n = head;
        int i = 0;
        while (n.next != null) {
            n = n.next;
            if (n.item.equals(t)) {
                return i;
            }
            i += 1;
        }
        return -1;
    }

    public void show() {
        Node<T> n = head;
        while (n.next != null) {
            n = n.next;
            System.out.print(n.item + " ");
        }
        System.out.println();
    }

    public void reverse() {
        // 检测是否为空链表，非空则递归调用有参的reverse方法
        if (isEmpty()) {
            return;
        }
        reverse(head.next);
    }

    // 反转指定节点，并返回
    public Node reverse(Node curr) {
        if (curr.next == null) {
            head.next = curr;
            return curr;
        }
        // 递归调用当前节点就是反转后的上一个节点
        Node pre = reverse(curr.next);
        // 让返回的节点的下一个节点成为当前节点
        pre.next = curr;
        // 把当前节点的下一个节点设置为null
        curr.next = null;
        return curr;
    }

    // 快慢指针获取链表中间值
    public void getMid() {
        Node n1 = this.head; // 快指针
        Node n2 = this.head; // 慢指针
        while (n1 != null && n1.next != null) {
            n1 = n1.next.next;
            n2 = n2.next;
        }
        System.out.println("链表中间值为：" + n2.item);
    }

    // 使用快慢指针判断链表是否有环
    public boolean isRing(){
        if (this.head == null) {
            return false;
        }
        /* 头节点不存储数据所以需要指定到头节点的下一个节点为起点 */
        Node n1 = this.head.next; // 快指针
        Node n2 = this.head.next; // 慢指针
        while (n1 != null && n1.next != null) {
            n1 = n1.next.next;
            n2 = n2.next;
            if(n1.equals(n2)){
                return true;
            }
        }
        return false;
    }

    // 构建环形链表 尾节点指向头节点即可
    public void ring(){
        if (this.head == null) {
            System.out.println("链表为空");
            return;
        }
        Node n = this.head;
        while (n.next!=null){
            n = n.next;
        }
        n.next = this.head.next;
    }

    // 通过快慢指针获取环入口
    public void isRingDoor(){
        if (this.head == null) {
            return;
        }
        /* 头节点不存储数据所以需要指定到头节点的下一个节点为起点 */
        Node n1 = this.head.next; // 快指针
        Node n2 = this.head.next; // 慢指针
        Node n3 = null; // 入口指针
        while (n1 != null && n1.next != null) {
            n1 = n1.next.next;
            n2 = n2.next;
            if(n1.equals(n2)){
               n3 = this.head.next;
               continue;
            }
            if(n3!=null){
                n3 = n3.next;
                if(n3.equals(n2)){
                    System.out.println("环入口节点"+n3.item);
                    break;
                }
            }
        }

    }
}
